Most data communications networks today rely heavily on shared-media, packet-based LAN technologies for both access and backbone connections. These networks use bridges and routers to connect multiple LANs into global internets.
A router-based, shared-media network cannot provide the high bandwidth and quality of service required by the latest networking applications and new faster workstations. For example, multimedia and full-motion video applications consume large amounts of bandwidth and require real-time delivery. Another high bandwidth application involves transmission of X-ray and other diagnostic information to enable doctors in different locations to consult while accessing the same patient information. Yet another application is "collaborative" engineering, i.e., allowing multiple engineers to work on the same project simultaneously while at different geographic locations. Thus, networks once used primarily for sending text files and E-mail or sharing common databases, are now being pushed to their limits as more users push more data across them.
One way to provide additional bandwidth on a given network segment is with larger shared-media pipes, such as FDDI or Fast Ethernet; however, this does not enable the application of policy or restricted access to the enhanced network resources. Alternatively, a network can be further segmented with additional router or bridge ports; however, this increases the cost of the network and the complexity of its management and configuration.
Switched networking is a proposed solution intended to provide additional bandwidth and quality of service. In such networks, the physical routers and hubs are replaced by switches and a management system is optionally provided for monitoring the configuration of the switches. The overall goal is to provide a scalable high-performance network where all links between switches can be used concurrently for connections.
One proposal is to establish a VLAN switch domain--a VLAN is a "logical" or "virtual" LAN in which users appear to be on the same physical (or extended) LAN segment, even though they may be geographically separated. However, many VLAN implementations restrict VLAN assignments to ports, rather than end systems, which limits the effectiveness of the VLAN groupings. Other limitations of existing VLAN implementations include excessive broadcast traffic (which consume both network bandwidth and end system CPU bandwidth), disallowing transmissions out of multiple ports, hop-by-hop switching determinations, and requiring multi-protocol routers to enable transmission between separate VLANs. Another problem with many VLAN switched networks is that although they allow a meshed topology, none of the redundant links can be active at the same time. Generally, the active links are determined by a spanning tree algorithm which finds one loop-free tree-based path through the network.
In computer networks and controllers, sharing of bandwidth-limited resources is commonly required. Bandwidth-limited resources may be hardware or software resources. Examples of bandwidth-limited, shared hardware resources are peripheral devices such as printers, scanners, memories, disk drives and backplane communication links. Backplane communications links are used to connect modules in a device, such as a computer, a network controller, or a network hub such as a bridge or a router. Examples of bandwidth-limited, shared software resources are processes such as compression/decompression algorithms, and memory access algorithms. These resources are referred to as bandwidth-limited because their bandwidth limits the rate at which data can be transferred to, from, or by the resource. The term bandwidth-limited, shared resource is meant to refer to a device or process having a bandwidth limit that determines the rate of transfer of data.
In a system such as a local area network bridge or router, a number of modules are contained in a chassis. Each of the modules has one or more ports which may be connected to users or other network segments. The modules are connected together via a backplane communications link over which data is transferred from one module to another resulting in the data being transferred from one port on one module to another port on another module. This backplane communications link, although typically having a high bandwidth and resulting high rate of data transfer (typically from several hundred megabits per second to several gigabits per second), is the limiting factor in determining how quickly data is transferred from one port on one module to another port on another module, because the backplane communications link can serve only one port at a time.
To ensure that all of the ports connected to the networking chassis have access to the backplane communications link, some type of arbitration is typically employed. Each of the ports on a module connected to the networking chassis may be considered a "competing device" that competes, along with all of the other ports connected to the networking chassis for access to the backplane communications link. The term "competing device" is meant to refer generally to any type of hardware device, software process, or firmware, or application program that is to make use of a bandwidth-limited, shared resource.
One approach to arbitrate between the competing devices has been to provide what is known as time division multiplexing (TDM). In a TDM arbiter, a time segment is determined. A time segment is a unit of time, typically fixed, during which a competing device would be allowed exclusive use of the bandwidth-limited, shared resource. One time segment is assigned for each competing device. If there were ten competing devices, then there would be ten time segments. Each of the competing devices is then assigned to one of the available time segments. This information is then used by a state machine that increments through each time segment to allow the particular competing device assigned to that segment to use the backplane communications link for its assigned time segment. After the state machine has stepped through all ten devices, the process loops back to the first segment and begins again. This results in each competing device being able to use one-tenth of the available bandwidth of the bandwidth-limited, shared resource.
In a TDM arbiter, the users of each time segment are fixed. For example, the first segment is always assigned to a particular port on the network chassis and the ninth segment is assigned to another particular port on the networking chassis. One of the problems with this type of arbiter is that if the port that is allocated a time segment is not requesting use of the backplane at that time, then that time segment will be wasted and the backplane communications link is idle during the assigned segment.
Another way to allocate the time segments of a bandwidth-limited, shared resource such as a backplane communications link is to use a so-called "Round-Robin" arbitration system. In a Round-Robin system, a list of the competing devices is compiled and stored. An allocation token allowing exclusive use of the backplane communications link is then passed among the list of competing devices, for example, in a sequential manner. By applying sets of rules to the allocation token, the token can be passed to a device that is not necessarily the next device in the list, thus allowing for some prioritizing of allocation among competing devices. The competing device that is in possession of the allocation token is then allowed to use the backplane communications link for a particular time period. One problem with this type of arbitration system is that if the device in possession of the allocation token does not require use of the backplane communications link, the backplane communication link is unused and idle for the particular time segment.
Other types of fixed allocation systems may be used that determine, at the beginning of a particular time segment, which competing device is to be allowed exclusive access to the backplane communications system. One problem with fixed allocation systems is that the arbitration requires a portion of the time segment to determine which competing device should use that particular time segment. Therefore, the rate at which data can be transmitted across the backplane communications link is reduced because a portion of the time segment must be used to perform arbitration.
Another disadvantage of the TDM and Round-Robin arbiters is that the latency of transmission of, for example, a data packet, may be increased due to the wasted time segments. That is, although a data packet from a particular port may be waiting and ready for transmission across the backplane communications link, the data packet cannot be transmitted until the TDM arbiter allows the port access to the backplane communications link or the Round-Robin token is allocated to the port.
One of the problems associated with these prior art systems is management lockout or the problem of the Network Management System (NMS) losing contact with the switch. This is undesirable because the network manager loses its ability to manage the switch. For example, the network manager would not be able to enforce a policy on time if the NMS could not "talk" to the switch due to its losing contact with the switch.
The problem of losing contact with the switch(es) is generally seen only under heavy load conditions. Under a heavy load, a majority of the network switches are busy switching the incoming packets leaving very minimal or no CPU time to process requests from a management station or to run other system processes. This problem can be seen on a majority of the switches using a single CPU because the systems are designed and developed to switch as many packets per second as possible with very little emphasis on executing other system processes.
For example, in bridge implementations, the entire bridging process is scheduled to run for every packet that is coming in and at a maximum load, so that the bridging process alone can take the entire bandwidth of a CPU. This may not be a problem for the bridge because the NMS plays very little or no role in running a bridge. However, an entire switch code can not be run as a single process because setting up a connection and/or enforcing a policy is more complicated. Also, on a switch device, the management functionality is as important as switching the packets and hence the subsystems handling the switching process and the other processes should be given a fair share of the CPU time.
Another problem is the number of connections a switch can set up in a given period of time. In a policy-based environment, every unknown packet received by the switch has to be examined and processed prior to setting up the connection. The processing steps include signalling the policy server, applying the policy, and if the policy allows the connection, setting up the connection on the switch. These steps have to be carried out as quickly as possible in order to process all of the incoming packets. If these processes are not allocated enough CPU bandwidth, the time required to set up a connection increases. This latency in setting up a connection may result in the need for retransmissions (that take extra network bandwidth) or a failure of the two systems to talk to one another (which may cause a failure of an application). For example, when a user on a sales department computer is trying to contact another system in the marketing department using a "ping" command, if the switch connecting those two computers fails to set up the connection on time, the "ping" command fails and the user assumes that the marketing system computer is down. To prevent these problems, the processes that sets up connections on a switch should be allocated the required CPU bandwidth on time.
Another problem is prioritizing. Consider a case where the switch has to process all the incoming packets while giving a slightly higher priority to IP packets. Usually, changing the process priorities depending on the real-time behavior of the system is difficult and is therefore not done.